{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Max Sum of a Pair With Equal Sum of Digits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数位和相等数对的最大和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的数组 <code>nums</code> ，数组中的元素都是 <strong>正</strong> 整数。请你选出两个下标 <code>i</code> 和 <code>j</code>（<code>i != j</code>），且 <code>nums[i]</code> 的数位和 与&nbsp; <code>nums[j]</code> 的数位和相等。</p>\n",
    "\n",
    "<p>请你找出所有满足条件的下标 <code>i</code> 和 <code>j</code> ，找出并返回<em> </em><code>nums[i] + nums[j]</code><em> </em>可以得到的 <strong>最大值</strong> <em>。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [18,43,36,13,7]\n",
    "<strong>输出：</strong>54\n",
    "<strong>解释：</strong>满足条件的数对 (i, j) 为：\n",
    "- (0, 2) ，两个数字的数位和都是 9 ，相加得到 18 + 36 = 54 。\n",
    "- (1, 4) ，两个数字的数位和都是 7 ，相加得到 43 + 7 = 50 。\n",
    "所以可以获得的最大和是 54 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [10,12,19,14]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>不存在满足条件的数对，返回 -1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [max-sum-of-a-pair-with-equal-sum-of-digits](https://leetcode.cn/problems/max-sum-of-a-pair-with-equal-sum-of-digits/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [max-sum-of-a-pair-with-equal-sum-of-digits](https://leetcode.cn/problems/max-sum-of-a-pair-with-equal-sum-of-digits/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[18,43,36,13,7]', '[10,12,19,14]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        def calculateSumOfDigits(num):\n",
    "            result = 0\n",
    "            while num > 0:\n",
    "                result += num % 10\n",
    "                num //= 10\n",
    "            return result\n",
    "        t = defaultdict(list)\n",
    "        for num in nums:\n",
    "            sumOfDigits = calculateSumOfDigits(num)\n",
    "            v = t[sumOfDigits]\n",
    "            v.append(num)\n",
    "            v.sort()\n",
    "            if len(v) > 2:\n",
    "                v.pop(0)\n",
    "        result = -1\n",
    "        for k, v in t.items():\n",
    "            if len(v) == 2:\n",
    "                result = max(result, sum(v))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        numss=nums.copy()\n",
    "        summ={}\n",
    "        n=len(nums)\n",
    "        for i in range(0,n):\n",
    "            flag=0\n",
    "            while nums[i]>0:\n",
    "                flag+=nums[i]%10\n",
    "                nums[i]=int(nums[i]/10)\n",
    "            if flag not in summ:\n",
    "                summ[flag]=[numss[i]]\n",
    "            else:\n",
    "                summ[flag].append(numss[i])\n",
    "        ans=-1\n",
    "        print(summ)\n",
    "        for i in summ.keys():\n",
    "            if len(summ[i])<2:\n",
    "                continue\n",
    "            summ[i].sort()\n",
    "            ans=max(ans,summ[i][-1]+summ[i][-2])\n",
    "            \n",
    "        return ans\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        ans=-1\n",
    "        d=defaultdict(int)\n",
    "        for num in nums:\n",
    "            s,x = 0, num\n",
    "            while x:\n",
    "                s+=x%10\n",
    "                x//=10\n",
    "            if s in d and num+d[s]>ans:\n",
    "                ans = num+d[s]\n",
    "            if num>d[s]:\n",
    "                d[s]=num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        plus = [0] * len(nums)\n",
    "        count = [1] * len(nums)\n",
    "        place = [0] * 82\n",
    "        max_num = -1\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            num = nums[i]\n",
    "            count = 0\n",
    "            while  num != 0:\n",
    "                count += num%10\n",
    "                num = num//10\n",
    "            if count in plus:\n",
    "                pos = place[count]\n",
    "                index = plus.index(count, pos)\n",
    "                place[count] = i\n",
    "                max_num = max(max_num, nums[i]+nums[index])\n",
    "                nums[i] = max(nums[i], nums[index])\n",
    "                \n",
    "            plus[i] = count\n",
    "        return max_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "\n",
    "        d = collections.defaultdict(list)\n",
    "        for i in range(len(nums)):\n",
    "            tt = nums[i]\n",
    "            t = 0 \n",
    "            while nums[i] > 0:\n",
    "                t += nums[i] % 10\n",
    "                nums[i] //= 10\n",
    "            if t not in d:\n",
    "                d[t].append(tt)\n",
    "            elif len(d[t]) == 1:\n",
    "                if tt > d[t][0]:\n",
    "                    d[t].append(d[t][0])\n",
    "                    d[t][0] = tt \n",
    "                else:\n",
    "                    d[t].append(tt)\n",
    "            elif len(d[t]) == 2:\n",
    "                if tt > d[t][0]:\n",
    "                    d[t][0], d[t][1] = tt, d[t][0]\n",
    "                elif tt > d[t][1]:\n",
    "                    d[t][1] = tt\n",
    "\n",
    "        ans = -1\n",
    "        for k, v in d.items():\n",
    "            if len(v) > 1:\n",
    "                ans = max(ans, v[0]+v[1])\n",
    "        return ans\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        plus = [0] * len(nums)\n",
    "        count = [1] * len(nums)\n",
    "        place = [0] * 82\n",
    "        max_num = -1\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            num = nums[i]\n",
    "            count = 0\n",
    "            while  num != 0:\n",
    "                count += num%10\n",
    "                num = num//10\n",
    "            if count in plus:\n",
    "                pos = place[count]\n",
    "                index = plus.index(count, pos)\n",
    "                place[count] = i\n",
    "                max_num = max(max_num, nums[i]+nums[index])\n",
    "                nums[i] = max(nums[i], nums[index])\n",
    "                \n",
    "            plus[i] = count\n",
    "        return max_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        dic = {}\n",
    "        for i in range(len(nums)):\n",
    "            sum1 = 0\n",
    "            temp = nums[i]\n",
    "            while nums[i] >= 1:\n",
    "                sum1 += nums[i] % 10\n",
    "                nums[i] //= 10\n",
    "            if sum1 not in dic:\n",
    "                dic[sum1] = [temp]\n",
    "            else:\n",
    "                dic[sum1].append(temp)\n",
    "        values = list(dic.values())\n",
    "        ans = 0\n",
    "        for i in range(len(values)):\n",
    "            if len(values[i]) >= 2:\n",
    "                values[i].sort(reverse = True)\n",
    "                ans = max(ans, values[i][0] + values[i][1])\n",
    "        return ans if ans != 0 else -1\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        num_dic = dict()\n",
    "        nums = sorted(nums)\n",
    "        for i in nums:\n",
    "            k = sum(map(int, list(str(i))))\n",
    "            if k not in num_dic.keys():\n",
    "                num_dic[k] = [i]\n",
    "            else:\n",
    "                num_dic[k].append(i)\n",
    "        if len(num_dic.keys()) == len(nums):\n",
    "            return -1\n",
    "        res = 0\n",
    "        for i in num_dic.keys():\n",
    "            if len(num_dic[i]) >= 2:\n",
    "                res = max(res, sum([num_dic[i][-1], num_dic[i][-2]]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        digit_sums = [0]*n\n",
    "        record = defaultdict(list)\n",
    "        nums.sort()\n",
    "        for i in range(n):\n",
    "            digit_sums[i] = sum(map(int, list(str(nums[i]))))\n",
    "            record[digit_sums[i]].append(i)\n",
    "        \n",
    "        res = 0\n",
    "        for key in record.keys():\n",
    "            idx_lst = record[key]\n",
    "            if len(idx_lst) > 1:\n",
    "                res = max(res, nums[idx_lst[-1]] + nums[idx_lst[-2]])\n",
    "\n",
    "        return res if res > 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        dfd=defaultdict(list)\n",
    "        for num in nums:\n",
    "            s=0\n",
    "            x=num\n",
    "            while num>0:\n",
    "                s+=num%10\n",
    "                num=num//10\n",
    "            dfd[s].append(x)\n",
    "            # s=sum(int(i) for i in str(num))\n",
    "            # dfd[s].append(num)\n",
    "        ans=-1\n",
    "        for i in dfd.values():\n",
    "            if len(i)>1:\n",
    "                i.sort()\n",
    "                ans=max(ans,i[-1]+i[-2])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        #找到每个数位和对应的最大的两个数字，因为数位和最大的范围是[0,81]\n",
    "        # dic[i][0] 第二大  dic[i][1] 第一大\n",
    "        dic = {i:[-1,-1] for i in range(82)}\n",
    "        for num in nums:\n",
    "            #得到num的数位和\n",
    "            tmp = num\n",
    "            bitSum = 0\n",
    "            while tmp != 0:\n",
    "                bitSum += tmp % 10\n",
    "                tmp //= 10\n",
    "            #大于第二大\n",
    "            if num > dic[bitSum][0]:\n",
    "                #大于第一大\n",
    "                if num > dic[bitSum][1]:\n",
    "                    dic[bitSum][0], dic[bitSum][1] = dic[bitSum][1], num\n",
    "                else: dic[bitSum][0] = num\n",
    "        \n",
    "        res = -1\n",
    "        for i in dic:\n",
    "            if dic[i][0] != -1:\n",
    "                res = max(res, dic[i][0] + dic[i][1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_digit(x):\n",
    "    res = 0\n",
    "    while x:\n",
    "        res += x % 10\n",
    "        x //= 10\n",
    "    return res\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        dic = defaultdict(list)\n",
    "        for x in nums:\n",
    "            dic[get_digit(x)].append(x)\n",
    "        return max([sum(sorted(lst)[-2:]) for lst in dic.values() if len(lst) >= 2], default=-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        hd = {}\n",
    "        for num in nums:\n",
    "            key = sum([int(x) for x in str(num)])\n",
    "            # print(temp)\n",
    "            if key in hd: # 只留最大两个数\n",
    "                temp = sorted(hd[key]+[num])\n",
    "                hd[key]=temp[-2:]\n",
    "            else:\n",
    "                hd[key] = [num]\n",
    "        res = -1\n",
    "        for t in hd:\n",
    "            print(t)\n",
    "            if len(hd[t])<2:\n",
    "                continue\n",
    "            res = max(sum(hd[t]),res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        resultSum = -1 \n",
    "        numsLen = len(nums)\n",
    "        bitSumMaxDict = {}\n",
    "\n",
    "        for i in range(0, numsLen):\n",
    "            bitSum = 0\n",
    "            currentNum = nums[i]\n",
    "\n",
    "            while(currentNum > 0):\n",
    "                bitSum += currentNum - int(currentNum/10) * 10\n",
    "                currentNum = int(currentNum / 10)\n",
    "\n",
    "            if bitSum in bitSumMaxDict:\n",
    "                currentSum = nums[i] + bitSumMaxDict[bitSum]\n",
    "\n",
    "                if currentSum > resultSum :\n",
    "                    resultSum = currentSum\n",
    "\n",
    "                if nums[i] > bitSumMaxDict[bitSum]:\n",
    "                    bitSumMaxDict[bitSum] = nums[i]\n",
    "\n",
    "            else :\n",
    "                bitSumMaxDict[bitSum] = nums[i]\n",
    "\n",
    "        return resultSum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        res = -1\n",
    "        d = defaultdict(lambda :[])\n",
    "        def sm(a):\n",
    "            return sum(int(x) for x in str(a))\n",
    "        for x in nums:\n",
    "            d[sm(x)].append(x)\n",
    "        for v in d.values():\n",
    "            if len(v)>=2:\n",
    "                v.sort()\n",
    "                res = max(res, v[-1]+v[-2])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        d = defaultdict(int)\n",
    "        res = -1\n",
    "        for i in nums:\n",
    "            digitsSum = sum(int(c) for c in str(i))\n",
    "            if digitsSum in d:\n",
    "                res = max(res, d[digitsSum] + i)\n",
    "                d[digitsSum] = max(d[digitsSum], i)\n",
    "            else:\n",
    "                d[digitsSum] = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        index2nums = {}\n",
    "        for num in nums:\n",
    "            index = sum([int(i) for i in str(num)])\n",
    "            if index not in index2nums:\n",
    "                index2nums[index] = []\n",
    "            index2nums[index].append(num)\n",
    "\n",
    "        max_sum = -1\n",
    "        for values in index2nums.values():\n",
    "            if len(values) >= 2:\n",
    "                max_sum = max(max_sum, sum(sorted(values, key=lambda x: -x)[:2]))\n",
    "\n",
    "        return max_sum\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
